
//https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/submissions/555893129/
   class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return root;
        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        TreeNode node1 = lowestCommonAncestor(root.left,p,q);
        TreeNode node2 = lowestCommonAncestor(root.right,p,q);
        if (node1 != null && node2 != null) {
            return root;
        }else {
            return node1 != null ? node1 : node2;
        }
    }
}